package leetcode101_xqzhao

// TODO 岛屿数量 【-】 递归

func numIslands(grid [][]byte) (ans int) {
	M, N := len(grid), len(grid[0])

	var dfs200 func(m, n int)
	dfs200 = func(m, n int) {
		// 停止递归条件
		if m < 0 || m >= M || n < 0 || n >= N || grid[m][n] != '1' { // grid[m][n] == '0' 会报内存溢出
			return
		}
		// 保存递归
		grid[m][n] = '2' // 标记已经访问过得陆地
		// 继续递归
		dfs200(m-1, n)
		dfs200(m+1, n)
		dfs200(m, n-1)
		dfs200(m, n+1)
	}

	for i := 0; i < M; i++ {
		for j := 0; j < N; j++ {
			if grid[i][j] == '1' {
				ans++
				dfs200(i, j)
			}
		}
	}
	return
}
